What is the worst case scenario for insertion sort O(n^2)?
it strikes me that if the array to be sorted is already sorted in reverse order then the first element is compared 0 times the second 1 time, the third 2 times and so on and so the total time should equal the SUM {i=1->i=(n-1)} [n] but that doesn't equal n^2 (for example if n=4 then that sum is 1+2+3=6.
this website says its because each insertion takes O(n) and theres n of those so thats O(n^2). but why does each insertion take O(n), the first one doesn't so onlyl n-1 insertions could take O(n) but neither does the second one and so on. only the insertions towards infinity take O(n) to insert. (is it becuase theres an infinite number of elements with insirtion=O(n) and so the oens where insertion takes
user541686 :
Your example is correct.\n\nO(n²) means proportional to n² as n approaches infinity, not necessarily equal n² for all n.\n\nMore precisely, to show that f(n) and g(n) are proportional as n grows to infinity, you need to show\n\n\\lim_{n\\to \\infty}\\frac{f(n)}{g(n)} = c http://www.texify.com/img/%5CLarge%5C%21%5Clim_%7Bn%5Cto%20%5Cinfty%7D%5Cfrac%7Bf%28n%29%7D%7Bg%28n%29%7D%20%3D%20c.gif\n\nfor some finite nonzero constant c. In this case, you get something like\n\n\\lim_{n\\to \\infty}\\frac{n^2}{\\left(\\frac{n^2+n}{2}\\right)} = 2 http://www.texify.com/img/%5CLarge%5C%21%5Clim_%7Bn%5Cto%20%5Cinfty%7D%5Cfrac%7Bn%5E2%7D%7B%5Cleft%28%5Cfrac%7Bn%5E2%2Bn%7D%7B2%7D%5Cright%29%7D%20%3D%202.gif",
2011-05-19T05:33:53